package com.xmg.day06;

/**
 * @Author: mazhongqing
 * @Date: 2020/10/27 10:06
 */
public class ArrLostDemo {

    public static void main(String[] args) {
        //默认从最右边开始计算 i=n-1 s=2
        int[] arr = {6, 0,0,0, 9};
        int count = 0;
        int N = arr.length;
        if (arr[N - 1] != 0) {
            count = deepCount(arr,N-1,arr[N-1],2);
        } else{
            for (int i = 1; i < 201; i++) {
                count += deepCount(arr,N-1,i,2 );
            }
        }
        System.out.println("共有"+count+"种可能");
    }
    /**
     *
     * @param arr 待计算数组
     * @param i   当前计算位置下表i
     * @param v   位置i期待值
     * @param s   i位置变成v之后i与i+1的对应关系
     *            s=0 arr[i]<arr[i+1]
     *            s=1 arr[i]=arr[i+1]
     *            s=2 arr[i]>arr[i+1]
     */
    public static int deepCount(int[] arr,int i,int v,int s){
        if(i==0){//已经到了数组第一位，需要满足<=arr[1]且arr[0]==0且arr[0]==v 其他状态均返回0
            return ((s==0||s==1)&&(arr[i]==0&&v==arr[i]))?1:0;
        }
        if(arr[i]!=0&&arr[i]!=v){//arr[i]没有丢失，不是0，且期望值与当前值不一样，直接返回0
            return 0;
        }
        int ways =0;
        if (s==0||s==1){//arr[i]<=arr[i+1] 此时必然满足 arr[i]<=max(arr[i-1],arr[i+1]),所以此时arr[i-1]位置可以任意变换
            for (int pre = 1; pre < 201; pre++) {
                ways += deepCount(arr,i-1,pre,pre<v?0:(pre==v?1:2));
            }
        }else{//arr[i]>arr[i+1] 此时必须满足 arr[i-1]>=arr[i],所以此时arr[i-1]的取值范围为 v~200
            for (int pre = v; pre < 201; pre++) {
                ways += deepCount(arr,i-1,pre,pre==v?1:2);
            }
        }
        return ways;
    }
}
